"""
[3,      1, 4, 2, 5, 7, 6, 8]
[1, 3,      4, 2, 5, 7, 6, 8]   1
[1, 3, 4,      2, 5, 7, 6, 8]   2
[1, 2, 3, 4,      5, 7, 6, 8]   3
[1, 2, 3, 4, 5,      7, 6, 8]   4
[1, 2, 3, 4, 5, 7,      6, 8]   5
[1, 2, 3, 4, 5, 6, 7, 8     ]   6
[1, 2, 3, 4, 5, 6, 7, 8]
"""


def insert_sort(li: list):
    n = len(li)
    for i in range(1, n):   # i 表示拿到的元素的下标
        j = i - 1           # 有序区要对比的元素
        while j >= 0 and li[j] > li[i]: # 如果摸到的元素比有序区的元素小，并且有序区有元素
            li[j+1] = li[j]
            j -= 1
        li[j+1] = li[i]
        print(li)
    return li

if __name__ == '__main__':
    alist = [3, 1, 4, 2, 5, 7, 6, 8]
    res = insert_sort(alist)
    print(res)
